package leetcode.Hot100;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author Cheng Jun
 * Description: 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 * <p>
 * 链接：https://leetcode-cn.com/problems/majority-element
 * @version 1.0
 * @date 2021/11/16 11:02
 */
public class majorityElement {
    public static void main(String[] args) {
        System.out.println(majorityElement1(new int[]{3, 3, 4}));
    }

    // hashmap 实现，key为 nums[i], value 为次数
    // 时间复杂度：O(n)，空间复杂度：O(n)
    static int majorityElement(int[] nums) {
        HashMap<Integer, Integer> numCountMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numCountMap.containsKey(nums[i])) {
                numCountMap.put(nums[i], numCountMap.get(nums[i]) + 1);
            } else {
                numCountMap.put(nums[i], 1);
            }
            if (numCountMap.get(nums[i]) > nums.length / 2) {
                return nums[i];
            }
        }
        return 0;
    }

    // 数组排序，然后取中间的数字
    static int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    // 摩尔投票法
    // Boyer-Moore 投票算法:如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来，显然和大于 0，
    // 从结果本身我们可以看出众数比其他数多。
    // 假定 第一个数为众数，然后下一个数和假定众数不一致，两者对撞掉，总数减一。如果一致总数 加一。总数为0 的时候，重新选定假定众数。
    // 最后一定是 假众数 变成了真的众数。

    // 算法思想：众数可以对撞掉所有的 非众数，最后剩下的还是众数，众数对撞过程中，有可能非众数和非众数对撞，这样最后也是剩下真正的众数。
    static int majorityElement3(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else {
                count += num == candidate ? 1 : -1;
            }
        }
        return candidate;
    }
}
